package org.example.myleet.p400;

/**
 * 思路：归纳推理
 * 考虑1～9有9个数，即9个数字；10～99有90个数，即180个数字；100～999有900个数，即2700个数字。。。以此类推
 * 因此，需要首先计算出超过n个数字所需要的最大数，总数字F(i) = F(i-1) + 9 * base * digit
 * 其中base是个、十、百...，digit是个、十、百...对应的数字个数，即1、2、3...
 * 然后再逆推回来
 */
public class Solution {
    public int findNthDigit(int n) {
        long start = 1, end = 9;
        int digit = 1, base = 1;
        //先寻找足够大的start
        while (end < n) {
            base = base * 10;
            ++digit;
            start = end + 1L;
            end = end + 9L * (long) base * (long) digit;
        }
        //根据start反推数字num以及num的第d位数字，然后转化成字符串获取对应的数字
        long t = n - start;
        long num = t / digit + base;
        long d = t % digit;
        String s = Long.toString(num);
        return s.charAt((int) d) - '0';
    }
}
